SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Warren Abstract Machine</title>

</head>

Warren Abstract Machine

</h1>

</header>

In 1983, <a href="David_H._D._Warren" title="David H. D. Warren">David H. D. Warren</a> designed an <a href="Abstract_machine" title="Abstract machine">abstract machine</a> for the execution of <a href="Prolog" title="Prolog">Prolog</a> consisting of a <a href="Computer_storage" class="mw-redirect" title="Computer storage">memory</a> architecture and an <a href="Instruction_set" class="mw-redirect" title="Instruction set">instruction set</a>.<a href="#cite_note-1">[1]</a><a href="#cite_note-2">[2]</a><a href="#cite_note-3">[3]</a> This design became known as the Warren Abstract Machine (WAM) and has become the de facto standard target for Prolog <a href="Compiler" title="Compiler">compilers</a>.

<div class="mw-heading mw-heading2"><h2 id="Purpose">Purpose</h2></div>

The purpose of compiling Prolog code to the more low-level WAM code is to make subsequent interpretation of the Prolog program more efficient. Prolog code is reasonably easy to translate to WAM instructions, which can be more efficiently interpreted. Also, subsequent code improvements and compilations to native code are often easier to perform on the more low-level representation.

In order to write efficient Prolog programs, a basic understanding of how the WAM works can be advantageous. Some of the most important WAM concepts are first argument indexing and its relation to choice-points, <a href="Tail_call_optimization" class="mw-redirect" title="Tail call optimization">tail call optimization</a>, and memory reclamation on failure.

<div class="mw-heading mw-heading2"><h2 id="Memory_areas">Memory areas</h2></div>

The WAM has the following memory areas:

<ul><li>The global stack or heap, used to store compound terms</li>

<li>The local stack for environment frames and choice-points</li>

<li>The trail to record which variables bindings ought to be undone on backtracking</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Example">Example</h2></div>

Here is a piece of Prolog code:

<div class="mw-highlight mw-highlight-lang-prolog mw-content-ltr" dir="ltr"><pre> girl(sally).

girl(jane).

boy(B) :- \+ girl(B).

</pre></div>

A WAM-based Prolog compiler will compile this into WAM instructions similar to the following:

<div class="mw-highlight mw-highlight-lang-prolog mw-content-ltr" dir="ltr"><pre> predicate(girl/1):

switch_on_term(2,1,fail,fail,fail),

label(1): switch_on_atom([(sally,3),(jane,5)])

label(2): try_me_else(4)

label(3): get_atom(sally,0)

proceed

label(4): trust_me_else_fail

label(5): get_atom(jane,0)

proceed

predicate(boy/1):

get_variable(x(1),0)

put_structure(girl/1,0)

unify_local_value(x(1))

execute((\+)/1)])

</pre></div>

An important characteristic of this code is its ability to cope with the various modes in which the predicates can be evoked: any argument might be a variable, a <a href="Ground_term" class="mw-redirect" title="Ground term">ground term</a>, or a partly instantiated term. The "switch" instructions handle the different cases.

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFDavid_H._D._Warren1983" class="citation book cs1">David H. D. Warren (October 1983). <a rel="nofollow" class="external text" href="https://www.sri.com/wp-content/uploads/2021/12/641.pdf">An abstract Prolog instruction set</a> (PDF). Menlo Park, CA, USA: <a href="Artificial_Intelligence_Center" title="Artificial Intelligence Center">Artificial Intelligence Center</a> at <a href="SRI_International" title="SRI International">SRI International</a>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20220619231625/https://www.sri.com/wp-content/uploads/2021/12/641.pdf">Archived</a> (PDF) from the original on 2022-06-19.</cite>

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> <cite id="CITEREFHassan_Aït-Kaci1999" class="citation book cs1 cs1-prop-unfit">Hassan Aït-Kaci (February 18, 1999). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20030213072337/http://www.vanx.org/archive/wam/wambook.pdf">Warren's Abstract Machine: A Tutorial Reconstruction</a> (PDF). Archived from the original on 2003-02-13.</cite>

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> <cite id="CITEREFHassan_Aït-Kaci" class="citation web cs1">Hassan Aït-Kaci. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20220119110941/http://wambook.sourceforge.net/">"Warren's Abstract Machine: A Tutorial Reconstruction; the book, errata and slides"</a>. Archived from <a rel="nofollow" class="external text" href="http://wambook.sourceforge.net/">the original</a> on 19 January 2022. Retrieved 7 March 2011.</cite>

</li>

</ol></div></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-06-15" href="https://en.wikipedia.org/wiki/?title=Warren_Abstract_Machine&oldid=1295764498">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>